package text111;

public class Solution41 {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    	//判断：root为空，或root等于p或者q的值，返回root
        if (root==null||root.val==p.val||root.val==q.val) {
			return root;
		}
        //记录遍历左右子树的值left，right
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        //判断：1、左为空 则p，q都在右子树上,返回右子树遍历结果
        // 		2、右为空 则p，q都在左子树上
        //		3、左右都不为空，则p，q分列左右子树两侧，返回root
        if (left==null) {
			return right;
		}
        else if (right==null) {
			return left;
		}else {
			return root;
		}	
    }
}
